package name.huzhenbo.java.algorithm.tree;

/**
 * http://baike.baidu.com/view/127820.htm
 * <p/>
 * http://www.blogjava.net/kafka0102/archive/2007/06/21/125469.html
 * <p/>
 * The current implementation assumes no duplicate weight.
 */
class HuffmanTree {
    private Node[] holder;

    public HuffmanTree(int[] input) {
        holder = new Node[input.length * 2 - 1];
        construct(input);
    }

    private void construct(int[] input) {
        for (int i = 0; i < input.length; i++) {
            holder[i] = new Node(input[i], -1, -1, -1, i);
        }
        for (int i = input.length; i < holder.length; i++) {
            parent(extractMinTwo(0, i - 1), i);
        }
    }

    private void parent(Node[] minTwo, int parentIndex) {
        holder[parentIndex] = new Node(minTwo[0].weight + minTwo[1].weight, -1, minTwo[0].index, minTwo[1].index, parentIndex);
        minTwo[0].parent = parentIndex;
        minTwo[1].parent = parentIndex;
    }

    private Node[] extractMinTwo(int start, int end) {
        Node min = new Node(Integer.MAX_VALUE, -1, -1, -1, -1);
        Node min2 = new Node(Integer.MAX_VALUE, -1, -1, -1, -1);
        for (; start <= end; start++) {
            Node current = holder[start];
            if (current.parent == -1) {
                if (current.weight < min2.weight){
                    min2 = current;
                    if (min2.weight < min.weight) {
                        Node temp = min;
                        min = min2;
                        min2 = temp;
                    }
                }
            }
        }
        Node[] result = {min, min2};
        return result;
    }

    public String code(int weight) {
        int i = 0;
        while(i < leafLength() && holder[i].weight != weight){
            i++;
        }
        StringBuilder result = new StringBuilder();
        if (i < leafLength()) {
            Node current = holder[i];
            while (current.parent != -1) {
                char currentCode = current.parent().lChild() == current ? '0' : '1';
                result.insert(0, currentCode);
                current = current.parent();
            }
        }
        return result.toString();
    }

    private int leafLength() {
        return (holder.length + 1) / 2;
    }

    private class Node {
        int weight;
        int parent;
        int lChild;
        int rChild;
        int index;

        public Node(int weight, int parent, int lChild, int rChild, int index) {
            this.weight = weight;
            this.parent = parent;
            this.lChild = lChild;
            this.rChild = rChild;
            this.index = index;
        }

        public Node parent() {
            return holder[parent];
        }

        public Node lChild() {
            return holder[lChild];
        }

        public Node rChild() {
            return holder[rChild];
        }
    }
}
